package com.kobeliu.entity;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/5 20:57
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
 *
 * 给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
 *
 * 如果可以构成，返回 true ；否则返回 false 。
 *
 * magazine 中的每个字符只能在 ransomNote 中使用一次。
 *
 *
 *
 * 示例 1：
 *
 * 输入：ransomNote = "a", magazine = "b"
 * 输出：false
 *
 * 示例 2：
 *
 * 输入：ransomNote = "aa", magazine = "ab"
 * 输出：false
 *
 * 示例 3：
 *
 * 输入：ransomNote = "aa", magazine = "aab"
 * 输出：true
 */
public class Demo_66_No383 {

    /**
     * 放入到hashmap中进行操作 O(M+N) (时间) O(n) 空间
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {

        int lenR = ransomNote.length();
        int lenM = magazine.length();
        if(lenR > lenM) return false;

        Map<Character,Integer> map = new HashMap<>();

        int i = 0;
        char c;
        for(;i<lenM;i++){
            c = magazine.charAt(i);
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
        i = 0;
        int num = 0;
        for(;i<lenR;i++){
            c = ransomNote.charAt(i);
            if(map.containsKey(c)){
                num = map.get(c);
                if(num>0){
                    map.put(c,num-1);
                }else{
                    return false;
                }

            }else{
                return false;
            }
        }
        return  true;
    }

    /**
     * 由于题中已经明确表示 为 26个小写字母，那么 打一个 26的表，做加减就行
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct1(String ransomNote, String magazine) {
        String str = String.valueOf('b');
        int[] arr = new int[26];
        for(char c:magazine.toCharArray()){
            arr[c-'a']++;
        }
        for(char c:ransomNote.toCharArray()){
            if(--arr[c-'a'] <0) return false;
        }
        return true;
    }


}
